package algorithms;

public class Tree {
	public Element head = null;
	
	public Element min(){
		Element current = head;
		while(current.left!=null){
			current = current.left;
		}
		return current;
	}
	
	public Element max(){
		Element current = head;
		while(current.right!=null){
			current = current.right;
		}
		return current;
	}
	
	
	public void add(Element elem){
		if(head==null){
			head = elem;
		}else{
			Element current = head;
			while(true){
				if (current.key>elem.key){
					if(current.left==null){
						current.left=elem;
						elem.parent=current;
						return;
					}else{
						current=current.left;
					}
				}
				if (current.key<elem.key){
					if(current.right==null){
						current.right=elem;
						elem.parent=current;
						return;
					}else{
						current=current.right;
					}
				}
			}
		}
	}
	public void print(Element elem, int count)
	{
		if(elem.right!=null)
		{
			print(elem.right,count+1);
		}
		for(int i=0; i<count; i++){
			System.out.print('\t');
		}
		System.out.println(elem.key);
		if(elem.left!=null)
		{
			print(elem.left,count+1);
		}
	}
	public void delete(Element elem, int a, char b)
	{
		if(elem.right!=null)
		{
			delete(elem.right,a,b);
		}
		
		if(elem.key == a && elem.value == b)
		{
			if(elem.left == null && elem.right == null)
			{
				//System.out.println("elem.left == null && elem.right == null");
				if(elem.parent!=null)
				{
					if(elem.parent.right == elem)
					{
						elem.parent.right = null;
					}
					if(elem.parent.left == elem)
					{
						elem.parent.left = null;
					}
				}
				else elem=null;
			}
			if(elem.right==null && elem.left!=null)
			{
				//System.out.println("elem.right==null && elem.left!=null");
				if(elem.parent!=null)
				{
					if(elem.parent.right == elem)
					{
						elem.parent.right = elem.left;
						elem.left.parent = elem.parent;
					}
					if(elem.parent.left == elem)
					{
						elem.parent.left = elem.left;
						elem.left.parent = elem.parent;
					}
				}
			}
			if(elem.right!=null && elem.left==null)
			{
				//System.out.println("elem.right!=null && elem.left==null");
				if(elem.parent!=null)
				{
				if(elem.parent.right == elem)
				{
					elem.parent.right = elem.right;
					elem.right.parent = elem.parent;
				}
				if(elem.parent.left == elem)
				{
					elem.parent.left = elem.right;
					elem.right.parent = elem.parent;
				}
			}
			}
			if(elem.right!=null && elem.left!=null)
			{
				//System.out.println("elem.right!=null && elem.left!=null");
				Element cur = elem.right;

				while(cur.left!=null)
				{
					cur=cur.left;
				}
				if(elem.parent!=null)
				{					
					if(elem.parent.left == elem)
					{
						cur.parent=elem.left;
						elem.parent.left=elem.left;
						cur.parent.right=cur;
					}
					if(elem.parent.right == elem)
					{
						cur.left=elem.left;
						if(cur.right==null)
						{
							elem.parent.right=cur.parent.left;
							cur.parent.left = null;
							cur.right=elem.right;
							
						}
						else
						{
							cur.left=elem.left;
							elem.parent.right=cur;
						}
						
						}
				}					
				else
				{						
					if(elem.right!=null)
					{
						elem.right.left=null;
						cur.right=elem.right;
						cur.right.parent=cur;
						elem.right=cur;
					}
					if(elem.left!=null)
					{
						elem.left.parent = cur;
						cur.left=elem.left;
					}
					head=cur;
				}
			}
		}
		if(elem.left!=null)
		{
			delete(elem.left,a,b);
		}
	}
}
